package com.example.demo.tree;

/**
 * Created by 蔡超 on 2018/10/9.
 */
public class SortDemo {

    public void bubble(Integer[] arr){
        int size = arr.length;
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size - i -1; j++) {
                if(arr[j] > arr[j+1]){
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
        }
        print(arr);
    }

    public void fast(Integer[] arr,int low,int high){
        int key = arr[low];
        int i = low;
        int j = high;
        while(i < j){

            while (i<j && arr[j] > key){
                j--;
            }
            while(i < j && arr[i] <= key){
                i++;
            }
            if(i<j){//交换
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
        //交换Key
        int tmp = arr[i];
        arr[i] = arr[low];
        arr[low] = tmp;
        print(arr);
    }

    public static void main(String[] args) {
        Integer[] arr = {10,20,15,0,6,7,2,1,-5,55};
        SortDemo sortDemo = new SortDemo();
//        sortDemo.bubble(arr);
        sortDemo.fast(arr,0,arr.length-1);
    }

    private static void print(Integer[] arr) {
        for (Integer integer : arr) {
            System.out.print(integer + ",");
        }
    }
}
